package week_04;

import java.util.*;

/**
 * 355. 设计推特
 * 设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，
 * 能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：
 * <p>
 * postTweet(userId, tweetId): 创建一条新的推文
 * getNewsFeed(userId): 检索最近的十条推文。
 * 每个推文都必须是由此用户关注的人或者是用户自己发出的。
 * 推文必须按照时间顺序由最近的开始排序。
 * follow(followerId, followeeId): 关注一个用户
 * unfollow(followerId, followeeId): 取消关注一个用户
 * <p>
 * 示例:
 * <p>
 * Twitter twitter = new Twitter();
 * <p>
 * // 用户1发送了一条新推文 (用户id = 1, 推文id = 5).
 * twitter.postTweet(1, 5);
 * <p>
 * // 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
 * twitter.getNewsFeed(1);
 * <p>
 * // 用户1关注了用户2.
 * twitter.follow(1, 2);
 * <p>
 * // 用户2发送了一个新推文 (推文id = 6).
 * twitter.postTweet(2, 6);
 * <p>
 * // 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5].
 * // 推文id6应当在推文id5之前，因为它是在5之后发送的.
 * twitter.getNewsFeed(1);
 * <p>
 * // 用户1取消关注了用户2.
 * twitter.unfollow(1, 2);
 * <p>
 * // 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文.
 * // 因为用户1已经不再关注用户2.
 * twitter.getNewsFeed(1);
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/design-twitter
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Twitter {
    public class Twitt {
        int val;
        Twitt next;
        int timestamp;

        Twitt() {
        }

        Twitt(int val) {
            this.val = val;
        }

        Twitt(int val, int timestamp) {
            this.val = val;
            this.timestamp = timestamp;
        }

    }

    public class TwittList {
        Twitt head;
        Twitt tail;

        public TwittList() {
            head = new Twitt();
            tail = new Twitt(-1);
            head.next = tail;
        }

        public void firstInsert(int val, int timestamp) {
            Twitt twitt = new Twitt(val, timestamp);
            twitt.next = head.next;
            head.next = twitt;
        }

        public Twitt getList() {
            return head.next;
        }
    }

    // 题意没有完全理解，必须加时间戳来区分先后，插入的id并不是单调递增
    Map<Integer, TwittList> userTweets = new HashMap<>();
    Map<Integer, Set<Integer>> follows = new HashMap<>();
    int timestamp = 0;

    /**
     * Initialize your data structure here.
     */
    public Twitter() {

    }

    /**
     * Compose a new tweet.
     */
    public void postTweet(int userId, int tweetId) {
        timestamp++;
        userTweets.computeIfAbsent(userId, key -> new TwittList()).firstInsert(tweetId, timestamp);
    }

    /**
     * Retrieve the 10 most recent tweet ids in the user's news feed.
     * Each item in the news feed must be posted by users who the user
     * followed or by the user herself.
     * Tweets must be ordered from most recent to least recent.
     */
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> ans = new ArrayList<>();

        PriorityQueue<Twitt> heap = new PriorityQueue<>(new Comparator<Twitt>() {
            @Override
            public int compare(Twitt o1, Twitt o2) {
                return o2.timestamp - o1.timestamp;
            }
        });
        // 加入用户自己
        if (userTweets.containsKey(userId)) {
            heap.add(userTweets.get(userId).getList());
        }
        // 加入用户follow
        if (follows.containsKey(userId)) {
            for (Integer followID : follows.get(userId)) {
                if (userTweets.containsKey(followID)) {
                    heap.add(userTweets.get(followID).getList());
                }

            }
        }
        // n 有序数组 求前k个值
        while (!heap.isEmpty()) {
            if (ans.size() >= 10) break;
            Twitt p = heap.poll();
            ans.add(p.val);
            if (p.next.val != -1) {
                heap.add(p.next);
            }
        }
        return ans;
    }

    /**
     * Follower follows a followee. I、 the operation is invalid, it should be a no-op.
     */
    public void follow(int followerId, int followeeId) {
        if (followeeId == followerId) {
            return;
        }
        follows.computeIfAbsent(followerId, key -> new HashSet<>()).add(followeeId);
    }

    /**
     * Follower unfollows a followee. If the operation is invalid, it should be a no-op.
     */
    public void unfollow(int followerId, int followeeId) {
        if (followeeId == followerId) {
            return;
        }
        // 互相删除——> 只取消关注
        if (follows.containsKey(followerId)) {
            follows.get(followerId).remove(followeeId);
        }

    }
}
